18장. 리스트, 큐, 스택, 링

지금까지 데이터를 묶는 방법으로 배열, 슬라이스, 맵, 구조체를 배웠다. 이 정도로도 웬만한 프로그램은 짤 수 있다.

하지만 실전에서는 더 특수한 모양의 자료구조가 필요할 때가 있다.

• 줄 서 있는 순서대로 꺼내는 큐 (FIFO)
• 가장 마지막에 넣은 것부터 꺼내는 스택 (LIFO)
• 노드들이 양쪽으로 연결된 이중 연결 리스트
• 끝없이 돌고 도는 원형 버퍼
• 가장 우선순위 높은 것부터 꺼내는 힙

이 장의 목표는 세 가지다.

• 슬라이스와 연결 리스트의 차이를 메모리 구조 차원에서 이해하기
• Go 표준 라이브러리의 container/* 패키지 활용법 익히기
• “이 상황엔 어떤 자료구조를 써야 하지?” 를 스스로 판단할 수 있게 되기

이 장에서는 Big-O 표기를 도구로 자주 쓴다. Big-O 자체에 대한 설명은 생략하니 표기가 낯설다면 다른 자료를 한 번 훑어보고 와도 좋다.

18.1 Go 표준 자료구조 한눈에 보기

Go 가 기본 제공하는 자료구조는 의외로 단출하다. 다음 표가 전부다.

언어 내장 세 가지가 90% 이상의 사용처를 커버한다. 나머지는 “필요할 때만 꺼내 쓰는” 도구다.

큐와 스택은 별도 자료형으로 제공되지 않는다. 슬라이스나 container/list 위에 직접 구현해서 쓴다.

18.2 메모리 구조부터 이해하기

자료구조의 성능 차이는 대부분 메모리에 어떻게 놓여 있는지에서 비롯된다. 슬라이스와 연결 리스트를 그림으로 비교해 보자.

슬라이스: 연속된 한 덩어리

슬라이스의 원소들은 메모리 위에 일렬로 붙어 있다.

인덱스:    0    1    2    3    4
주소:    0x10 0x14 0x18 0x1c 0x20
값:    [ 10 | 20 | 30 | 40 | 50 ]

이 구조의 장점은 분명하다.

• 인덱스로 즉시 접근 (s[i]) — O(1)
• CPU 캐시에 친화적

대신 약점도 분명하다.

• 중간에 끼워 넣으려면 뒷부분을 전부 밀어야 한다 — O(n)
• 앞에서 빼면 더 비싸다 — O(n)

연결 리스트: 흩어진 노드들

연결 리스트의 노드들은 메모리 곳곳에 흩어져 있고, 각자 다음 노드를 가리키는 포인터를 들고 있다.

[10 | →] ──→ [20 | →] ──→ [30 | →] ──→ [40 | →] ──→ nil
0x100       0x238       0x4a0       0x812

장점은 정반대다.

• 노드 사이에 끼워 넣기 — 포인터만 바꾸면 끝, O(1)
• 노드 제거 — 마찬가지로 O(1) (해당 노드를 알고 있을 때)

대신 약점도 정반대다.

• “5번째 요소“를 찾으려면 처음부터 따라가야 한다 — O(n)
• 메모리가 흩어져 있어 캐시 미스가 잦다

왜 보통 슬라이스가 더 빠른가

이론적으로 연결 리스트의 삽입은 O(1) 이고 슬라이스의 삽입은 O(n) 이지만, 실제로 측정해 보면 슬라이스가 빠른 경우가 많다.

이유는 캐시다.

• CPU 는 메모리에서 데이터를 한 줄(cache line) 통째로 가져온다
• 슬라이스는 인접한 원소가 함께 캐시에 올라온다
• 연결 리스트는 다음 노드가 어디 있을지 모르니 매번 메인 메모리까지 다녀와야 한다

이 차이는 작아 보여도 누적되면 100배까지 벌어진다. “이론적 복잡도“와 “실측 성능“은 다를 수 있다는 점을 기억해 두자.

그래서 Go 진영에서는 “특별한 이유가 없으면 슬라이스를 써라” 라는 조언이 거의 격언처럼 통한다.

18.3 이중 연결 리스트: container/list

그럼에도 연결 리스트가 빛나는 상황은 있다.

• 리스트 중간에서 자주 삽입/삭제가 일어날 때
• LRU 캐시처럼 “방금 쓴 노드를 맨 앞으로 이동” 이 잦을 때
• 거대한 데이터를 슬라이스 재할당 없이 유지하고 싶을 때

이럴 땐 container/list 가 답이다. 양방향으로 연결된 이중 연결 리스트를 제공한다.

기본 사용법

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()

	l.PushBack(10)  // 뒤에 추가
	l.PushBack(20)
	l.PushFront(5)  // 앞에 추가

	// 순회
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}
}

출력:

5
10
20

주요 메서드

노드와 값

PushBack 등은 새 노드 *list.Element 를 반환한다. 이 노드를 보관해 두면 나중에 O(1) 로 이동/삭제할 수 있다.

l := list.New()
e1 := l.PushBack("apple")
e2 := l.PushBack("banana")
l.PushBack("cherry")

l.MoveToFront(e2)       // banana 가 맨 앞으로
l.Remove(e1)            // apple 제거

for e := l.Front(); e != nil; e = e.Next() {
	fmt.Println(e.Value)
}
// banana
// cherry

Value 의 정체

e.Value 의 타입은 any 다. 어떤 값이든 넣을 수 있지만, 꺼낼 때 타입 단언이 필요하다.

e := l.Front()
s := e.Value.(string)  // string 으로 타입 단언
fmt.Println(len(s))

container/list 는 제네릭 도입 전부터 존재했다. 그래서 any 기반이다. 타입 안전이 중요하다면 17장의 제네릭으로 직접 래퍼를 만드는 편이 낫다.

18.4 큐 (FIFO) 구현하기

큐(Queue)는 “먼저 들어간 게 먼저 나온다” 규칙이다. 영어 두문자로 FIFO (First-In-First-Out).

은행 창구 줄, 프린터 작업 대기열 등이 큐다.

슬라이스로 구현 — 간단하지만 함정 있음

package main

import "fmt"

func main() {
	queue := []int{}

	// enqueue
	queue = append(queue, 1)
	queue = append(queue, 2)
	queue = append(queue, 3)

	// dequeue
	first := queue[0]
	queue = queue[1:]

	fmt.Println(first)  // 1
	fmt.Println(queue)  // [2 3]
}

append 로 뒤에 넣고 queue[1:] 로 앞을 잘라낸다. 짧고 직관적이다.

하지만 숨은 함정이 있다.

queue := make([]int, 0, 1000)
for i := 0; i < 1000; i++ {
	queue = append(queue, i)
}
for i := 0; i < 1000; i++ {
	queue = queue[1:]  // 앞을 자르기만 한다
}

// queue 는 비었지만…
// 원래 1000칸짜리 배열은 여전히 메모리에 남아 있다

queue[1:] 는 배열의 “창문“만 이동시킬 뿐 실제로 0번째 요소를 메모리에서 지우지 않는다. 오래 돌리는 프로그램에선 메모리 누수가 된다.

해결책은 세 가지다.

1. 가끔 copy 로 새 슬라이스에 옮기기
2. 큐가 비었을 때 queue = queue[:0] 으로 리셋
3. 링 버퍼(원형 버퍼)를 직접 구현

링 버퍼는 같은 배열의 두 인덱스 (head, tail) 를 모듈러 연산으로 돌리는 방식이다. 복잡도가 올라가는 만큼 여기선 개념만 짚는다.

실무에서는 큐가 늘 작거나, 큐 사용 패턴이 “잠깐 쌓였다가 비워지는” 식이면 슬라이스 그대로 써도 충분하다.

container/list 로 구현

연결 리스트는 앞에서 빼고 뒤에 넣는 게 둘 다 O(1) 이다. 큐 구현에 자연스럽게 어울린다.

package main

import (
	"container/list"
	"fmt"
)

type Queue struct {
	l *list.List
}

func NewQueue() *Queue {
	return &Queue{l: list.New()}
}

func (q *Queue) Enqueue(v any) {
	q.l.PushBack(v)
}

func (q *Queue) Dequeue() (any, bool) {
	front := q.l.Front()
	if front == nil {
		return nil, false
	}
	q.l.Remove(front)
	return front.Value, true
}

func (q *Queue) Len() int {
	return q.l.Len()
}

func main() {
	q := NewQueue()
	q.Enqueue("first")
	q.Enqueue("second")
	q.Enqueue("third")

	for q.Len() > 0 {
		v, _ := q.Dequeue()
		fmt.Println(v)
	}
}

출력:

first
second
third

15장에서 배운 메서드, 14장에서 배운 포인터 리시버를 그대로 활용한 모양이다.

18.5 스택 (LIFO) 구현하기

스택(Stack)은 “나중에 들어간 게 먼저 나온다” 규칙이다. 영어 두문자로 LIFO (Last-In-First-Out).

쌓아 둔 책 더미, 함수 호출 스택, “되돌리기(Undo)” 기능 등이 스택이다.

슬라이스로 깔끔하게

스택은 슬라이스로 짜는 게 가장 자연스럽다. 앞을 건드릴 일이 없어 큐의 함정에서 자유롭다.

package main

import "fmt"

func main() {
	stack := []int{}

	// push
	stack = append(stack, 1)
	stack = append(stack, 2)
	stack = append(stack, 3)

	// pop
	n := len(stack)
	top := stack[n-1]
	stack = stack[:n-1]

	fmt.Println(top)   // 3
	fmt.Println(stack) // [1 2]
}

append 로 뒤에 쌓고 마지막 인덱스를 꺼낸 뒤 슬라이스를 한 칸 줄인다. 두 연산 모두 평균 O(1) 이다.

제네릭 스택

17장에서 본 제네릭으로 타입 안전한 스택을 만들 수 있다.

package main

import "fmt"

type Stack[T any] struct {
	data []T
}

func (s *Stack[T]) Push(v T) {
	s.data = append(s.data, v)
}

func (s *Stack[T]) Pop() (T, bool) {
	var zero T
	n := len(s.data)
	if n == 0 {
		return zero, false
	}
	top := s.data[n-1]
	s.data = s.data[:n-1]
	return top, true
}

func (s *Stack[T]) Peek() (T, bool) {
	var zero T
	n := len(s.data)
	if n == 0 {
		return zero, false
	}
	return s.data[n-1], true
}

func (s *Stack[T]) Len() int {
	return len(s.data)
}

func main() {
	s := &Stack[string]{}
	s.Push("a")
	s.Push("b")
	s.Push("c")

	for s.Len() > 0 {
		v, _ := s.Pop()
		fmt.Println(v)
	}
}

출력:

c
b
a

• 타입 매개변수 T any 로 어떤 타입이든 담을 수 있다
• var zero T 로 T 의 제로값을 안전하게 만든다
• 호출 측이 타입 단언을 할 필요가 없다

Pop 이 두 값을 돌려주는 패턴은 Go 에서 매우 흔한 관용구다. “값 + 성공 여부” 또는 “값 + 에러” 형태.

18.6 원형 자료구조: container/ring

container/ring 은 양방향 원형 연결 리스트다. “끝이 처음으로 이어진” 모양을 떠올리면 된다.

 ┌──→ [A] ──→ [B] ──→ [C] ──→ [D] ──┐
 │                                   │
 └───────────────────────────────────┘

라운드 로빈(돌아가며 처리하기) 같은 용도에 어울린다.

기본 사용법

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	r := ring.New(4)  // 길이 4 짜리 링 생성

	// 모든 자리에 값 채우기
	for i := 0; i < r.Len(); i++ {
		r.Value = i + 1
		r = r.Next()
	}

	// 한 바퀴 출력
	r.Do(func(v any) {
		fmt.Println(v)
	})
}

출력:

1
2
3
4

주요 메서드

라운드 로빈 예제

서버 3대에 요청을 번갈아 보낸다고 해 보자.

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	servers := ring.New(3)
	for _, name := range []string{"A", "B", "C"} {
		servers.Value = name
		servers = servers.Next()
	}

	// 7번 요청을 분배
	for i := 0; i < 7; i++ {
		fmt.Printf("요청 %d → 서버 %v\n", i, servers.Value)
		servers = servers.Next()
	}
}

출력:

요청 0 → 서버 A
요청 1 → 서버 B
요청 2 → 서버 C
요청 3 → 서버 A
요청 4 → 서버 B
요청 5 → 서버 C
요청 6 → 서버 A

Next() 가 반환하는 새 노드를 변수에 다시 대입해야 한다. 안 그러면 같은 자리에서 계속 맴돈다.

18.7 우선순위 큐: container/heap 맛보기

우선순위 큐는 “가장 우선순위 높은 것부터 꺼내는” 큐다. 긴급한 작업 먼저 처리하기, 다익스트라 알고리즘 등에 쓰인다.

Go 는 container/heap 으로 최소 힙의 토대를 제공한다. 직접 자료구조를 들고 있지는 않다. 대신 heap.Interface 만 만족시키면 어떤 컬렉션이든 힙처럼 다룰 수 있게 해 준다.

heap.Interface

type Interface interface {
	sort.Interface          // Len, Less, Swap
	Push(x any)
	Pop() any
}

이 다섯 메서드만 구현하면 힙으로 동작한다.

정수 최소 힙 예제

package main

import (
	"container/heap"
	"fmt"
)

// IntHeap 은 정수 슬라이스 위에 만든 최소 힙
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	h := &IntHeap{5, 1, 4, 2, 3}
	heap.Init(h)

	heap.Push(h, 0)

	for h.Len() > 0 {
		fmt.Println(heap.Pop(h))
	}
}

출력:

0
1
2
3
4
5

작은 수부터 차례로 나온다.

동작 흐름

핵심 포인트:

• Less 의 반환값을 뒤집으면 최대 힙이 된다
• Push/Pop 메서드는 slice 자체 조작만 한다
• 힙 속성은 heap.Push / heap.Pop 이 알아서 유지한다

처음 보면 메서드가 두 종류로 갈리는 게 헷갈린다. 소문자 Push / Pop 은 내부 구현용, heap.Push(h, x) 가 우리가 호출하는 외부 API다.

18.8 연산별 속도 비교표

각 자료구조의 연산별 평균 시간 복잡도를 비교해 본다.

표 읽는 법

• “맨 앞 제거” 는 슬라이스가 O(n) 이지만, 앞에서 본 queue[1:] 트릭으로 O(1) 처럼 쓸 수 있다 (단, 메모리 누수 주의)
• container/list 의 “중간 삽입 O(1)” 은 삽입 위치 노드를 이미 갖고 있을 때만 성립한다
• 맵의 “—” 는 그 연산이 의미 없거나 비효율적이라는 뜻

그래서 결론은

대부분의 경우 슬라이스가 가장 빠르다. 이론적 복잡도가 약간 불리해도 캐시 친화성이 그 차이를 메우고도 남는다.

다음 두 경우에만 다른 도구를 고려하면 된다.

• 키로 빠르게 찾고 싶다 → 맵
• 중간 노드 위치를 들고 자주 옮기고 싶다 → container/list

18.9 어떤 걸 언제 쓰나

상황별 추천을 표로 정리한다.

결정 흐름도

어떤 연산이 가장 자주 일어나는가?

├─ 인덱스로 접근 → 슬라이스
├─ 키로 조회 → 맵
├─ "맨 뒤에 넣고 맨 뒤에서 꺼냄" → 슬라이스 (스택)
├─ "맨 뒤에 넣고 맨 앞에서 꺼냄"
│  ├─ 데이터가 짧게 머무름 → 슬라이스
│  └─ 데이터가 오래 누적됨 → container/list
├─ "가장 작은/큰 것부터 꺼냄" → container/heap
└─ "끝없이 순환" → container/ring

흔히 보이는 안티패턴

• 그냥 슬라이스로 충분한데 container/list 를 쓰는 경우 (대부분 손해다)
• 슬라이스를 그대로 큐로 쓰고 메모리 누수를 방치하는 경우
• 키 검색이 잦은데 슬라이스를 선형 탐색하는 경우 (요소가 100개를 넘으면 거의 맵이 낫다)

18.10 정리

이 장에서 본 내용:

• Go 표준 자료구조는 단출하다 — 슬라이스, 맵 + container/*
• 슬라이스는 연속 메모리, 연결 리스트는 흩어진 노드
• 대부분의 경우 캐시 친화성 덕분에 슬라이스가 더 빠르다
• container/list 는 이중 연결 리스트
  • 중간 삽입/삭제가 잦거나 노드 이동이 잦을 때
• 큐는 슬라이스 또는 container/list 로 만든다
  • 슬라이스 큐의 메모리 누수 함정 조심
• 스택은 슬라이스가 자연스럽다
• 제네릭으로 타입 안전한 스택을 깔끔하게 만들 수 있다
• container/ring 은 라운드 로빈용 원형 리스트
• container/heap 으로 우선순위 큐를 만든다
  • heap.Interface 만 만족시키면 된다
• “특별한 이유 없으면 슬라이스” 가 Go 진영의 격언

이로써 “여러 데이터를 어떻게 묶어 다루느냐“의 큰 그림이 끝난다. 다음 장에서는 맵의 내부 구조를 더 깊이 들여다본다. “왜 맵은 그렇게 빠른가”, “왜 순회 순서가 매번 달라지는가” 같은 질문에 답할 차례다.